Routing devices in packet switching networks route data packets from one routing device to another until the packets reach their final destination. Routing devices often receive packets at a rate that temporarily exceeds the rate at which the packets can be forwarded, and, consequently, routing devices employ arbitration schemes to determine which packets will be sent at a select time.
Packet switching networks use a variety of arbitration schemes, such as fixed priority or rotating schemes. Conventional arbitration schemes are limited, however, in that they do not ensure that the next destination routing device has capacity to receive a data packet before allowing the data packet to be outputted. Consequently, limited output resources are often wasted on transactions incapable of completion. Moreover, many conventional arbitration schemes are not easily or economically implemented in hardware, which provides for substantially higher performance than microprocessorbased schemes.
In Asynchronous Transfer Mode (ATM) networks, routing devices that estimate the storage capacity of the next destination routing device are known. The estimation is based on the available bandwidth of the network and the rate at which packets are being transmitted. This estimation method is limited, however, in that it does not keep track of the exact amount of space available in the next destination routing device, and, thus, cannot guarantee that sufficient space is available. Consequently, packets are sometimes sent to a routing device unable to receive the packet, and such errors can significantly reduce network performance. The risk of such errors is proportional to the transmission rate, and, thus, to minimize the risk, the packet transmission rate must be reduced. This limitation is particularly severe in multiprocessor-based packet switching networks because multiprocessor-based networks transmit data packets at a significantly greater rate than do ATM networks.
Moreover, when an arbiter employs a fixed priority arbitration scheme, it is desirable to ensure that sufficient space not only exists for the packet, but also for future higher priority traffic. Otherwise, lower priority traffic may delay higher priority traffic. The method used in ATM networks is limited in that it does not ensure that sufficient space exists for a higher priority packets before transmitting a lower priority packet. Therefore, a need exists for an arbitration method in a packet switching network that only allows a data packet access to an output if the next destination routing device has capacity to receive both the packet and, if applicable, future higher priority packets. Additionally, it is desirable to have an arbitration method that can be economically implemented in hardware.